package 剑指offer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by lenovo】 on 2017/3/1.
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class PrintPermutationAndCombinationOfString {
    ArrayList<String> arrayList = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        char []charStr = str.toCharArray();
        int len = charStr.length;
        Permutation(charStr , 0 , len - 1);
        Collections.sort(arrayList);
        return arrayList;
    }

    /**
     * 排 abcd
     * 1. a在第一位，bcd全排列；b在第一位，acd全排列；c在第一位，abd全排列；d在第一位，abc全排列
     * 排 bcd；排acd；排abd；排abc；
     * 1. 重复逻辑
     * 直到排最后一位
     * @param c
     */
    public void Permutation (char[] c, int row, int cloumn) {

        if(row == cloumn){         //一到递归的出口就输出数组，此数组为全排列
            String temp = new String(c);
            if (arrayList.contains(temp)) {
                return;
            }
            arrayList.add(new String(c));
            System.out.println(new String(c));
            return;
        }else {
            for (int j = row ; j <= cloumn; j++) {
                /* 第1次是swap(c , 0 , 1)
                      1.1 swap(c , 1 , 2)
                      1.2 swap(c , 1 , 3)
                   第2次是swap(c , 0 , 1)
                   第3次是swap(c , 0 , 2)
                */
                swap(c, row, j);
                Permutation(c, row + 1, cloumn);
                swap(c, row,j);
            }
        }
    }
    public void swap(char [] c , int  s1, int s2) {
        char temp = c[s1];
        c[s1] = c[s2];
        c[s2] = temp;
    }
    //   public void Permutation (char[] c, int row, int cloumn) {
//       for (int i = row ; i <= cloumn; i++) {
//           swap(c , row , i);
//           if (arrayList.contains(new String(c))) {
//               continue;
//           }
//           arrayList.add(new String(c));
//           Permutation(c , row+ 1 , cloumn );
//           swap(c , row , i);
//       }
//   }
    public int Number(int n) {

        if (n == 1) {
            return n;
        }
        return n * Number(n - 1);
    }
}
